﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 二分查找
{
    class Program
    {
        static void Main(string[] args)
        {
            /*  1  2  3  4  5  6  7  8  9 10 11
             * 12 21 30 35 38 40 48 55 56 60 64 在数组r当中，已经排好了顺序
             * 现在在数据里面查找 k = 50
             * int i = 1; int j = 11;
             * m = (i + j) / 2 = 6; r[m] = r[6] < k :在右半部分继续查找
             * 
             * i = m + 1 = 7; j = 11;
             * m = (i + j) / 2 = 9; r[m] = r[9] > k :在左半部分继续查找
             * 
             * i = 7; j = m - 1 = 8;
             * m = (i + j) / 2 = 7; r[m] = r[7] < K :在右半部份继续寻找
             * 
             * i = m + 1 = 8; j = 8;
             * m = (i + j) / 2 = 8; r[m] = r[8] > k :在左半部分继续寻找
             * 
             * i = 8; j = m - 1 = 7;
             * j < i => 查找失败
             * 
             */

            int[] intArray = { 12, 21, 30, 35, 38, 40, 48, 55, 56, 60, 64 };
            int key = int.Parse(Console.ReadLine());
            int low = 0;
            int high = intArray.Length - 1;
            
            while (low <= high)
            {
                int mid = (low + high) / 2;
                if (intArray[mid] == key)
                {
                    Console.WriteLine("find key, index = {0}", mid);
                    break;
                }
                else if (intArray[mid] > key)
                {// 如果中间的值大于要找的数，把后边的一半数组去掉，从左边找
                    high = mid - 1;
                }
                else
                {// 如果中间的值小于要找的数，把前边的一半数组去掉，从右边找
                    low = mid + 1;
                }
            }
        }
    }
}
